//! ## 14. Longest Common Prefix (easy, string)
//!
//! Write a function to find the longest common prefix string amongst an array of strings.
//!
//! If there is no common prefix, return an empty string `""`.
//! #### Example 1:
//! ```txt
//! Input: strs = ["flower","flow","flight"]
//! Output: "fl"
//! ```
//! #### Example 2:
//! ```txt
//! Input: strs = ["dog","racecar","car"]
//! Output: ""
//! Explanation: There is no common prefix among the input strings.
//! ```
//! #### Constraints:
//! - `0 <= strs.length <= 200`
//! - `0 <= strs[i].length <= 200`
//! - `strs[i]` consists of only lower-case English letters.
//!
//! ### 知识点
//! - 迭代器
//!     - map() 将一个迭代器转为另一个迭代器, 接收一个闭包参数
//!     - min() 迭代消耗器, 计算迭代器中最小的那个元素
//!     - all() 迭代消耗器, 接收一个闭包, 所有返回 true 才 true.
//! - 二维数组

pub struct Solution;

impl Solution {
    /// #### 原理
    /// 转为字符的二维数组然后进行比较
    /// #### 流程
    /// let ss: Vec<Vec<char>>
    /// let n = 最短那个字符串的长度
    /// let prefix = vec![];
    /// for i in 0..n {
    ///     let c = ss[0][i];
    ///     所有字符数组[i] 与 c 比较是否相等:
    ///         如果不相等, 跳出
    ///         如果相等, prefix.push(c)
    /// }
    /// #### 边界分析
    /// 传入空的字符串数组, 直接返回 "";
    /// #### 复杂度
    /// - 时间复杂度
    ///     - 有个双重循环 O(n*m) n 最短字符串长度, m 字符串数组长度
    /// - 空间复杂度
    ///     - 需要使用二维字符串数组作为额外存储 O(n*m) n 是字符串平均长度, m 字符串数组长度
    pub fn solve(strs: Vec<String>) -> String {
        if strs.len() == 0 {
            return String::new();
        }
        // 转为 Vec<Vec<char>>
        let ss: Vec<Vec<char>> = strs.iter().map(|s| s.chars().collect()).collect();
        // 最短那个字符串长度
        let n = ss.iter().map(|s| s.len()).min().unwrap();
        let mut prefix: Vec<char> = vec![];
        for i in 0..n {
            let c = ss[0][i];
            // 比较所有 Vec<char> 第 i 个字符是否与 c 相等
            if ss.iter().all(|s| s[i] == c) {
                prefix.push(c);
            } else {
                break;
            }
        }
        prefix.iter().collect()
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use myutils::vec_string;

    #[test]
    fn test() {
        let ss: Vec<String> = vec_string!["flower", "flow", "flight"];
        assert_eq!(Solution::solve(ss), String::from("fl"));
    }
}
